// https://leetcode.cn/problems/gray-code/




/*
n = 0, [0]
n = 1, [0,1] //新的元素1，为0+2^0
n = 2, [0,1,3,2] // 新的元素[3,2]为[0,1]->[1,0]后分别加上2^1
n = 3, [0,1,3,2,6,7,5,4] // 新的元素[6,7,5,4]为[0,1,3,2]->[2,3,1,0]后分别加上2^2->[6,7,5,4]
*/

#include <iostream>
#include <vector>
#include <math.h>


using namespace std;

class Solution {
public:
    vector<int> grayCode(int n) {
		vector<int> res(pow(2, n));
		res[0] = 0;
		for(int i = 1; i <= n; i++){
			int size = pow(2, i-1);
			for(int j = 0 ; j < size; j++){
				res[size + j] = res[size - j - 1] + size;
			}
		}
		return res;
    }
};

int main(){
	Solution so;
	auto a = so.grayCode(4);
	for(auto i : a){
		cout << i << ",";
	}
	cout << endl;
	return 0;
}